The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

sum(cons(s(n), x), cons(m, y)) → sum(cons(n, x), cons(s(m), y))
sum(cons(0, x), y) → sum(x, y)
sum(nil, y) → y
weight(cons(n, cons(m, x))) → weight(sum(cons(n, cons(m, x)), cons(0, x)))
weight(cons(n, nil)) → n

Rewrite Strategy: INNERMOST

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(n¹):
The rewrite sequence
sum(cons(s(n), x), cons(m, y)) →⁺ sum(cons(n, x), cons(s(m), y))
gives rise to a decreasing loop by considering the right hand sides subterm at position [].
The pumping substitution is [n / s(n)].
The result substitution is [m / s(m)].

(2) BOUNDS(n^1, INF)